//给你二叉树的根节点 root ，返回它节点值的 前序 遍历。 
//
// 
//
// 示例 1： 
//
// 
// 输入：root = [1,null,2,3] 
// 
//
// 输出：[1,2,3] 
//
// 解释： 
//
// 
//
// 示例 2： 
//
// 
// 输入：root = [1,2,3,4,5,null,8,null,null,6,7,9] 
// 
//
// 输出：[1,2,4,5,6,7,3,8,9] 
//
// 解释： 
//
// 
//
// 示例 3： 
//
// 
// 输入：root = [] 
// 
//
// 输出：[] 
//
// 示例 4： 
//
// 
// 输入：root = [1] 
// 
//
// 输出：[1] 
//
// 
//
// 提示： 
//
// 
// 树中节点数目在范围 [0, 100] 内 
// -100 <= Node.val <= 100 
// 
//
// 
//
// 进阶：递归算法很简单，你可以通过迭代算法完成吗？ 
//
// Related Topics 栈 树 深度优先搜索 二叉树 👍 1361 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-10-29 23:20:01
 * @description 144.二叉树的前序遍历
 */
public class BinaryTreePreorderTraversal{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 BinaryTreePreorderTraversal fun=new BinaryTreePreorderTraversal();
	 	 Solution solution = fun.new Solution();
         TreeNode treeNode = new TreeNode(1,


                 new TreeNode(2,
                         new TreeNode(4),
                         new TreeNode(5,
                                 new TreeNode(6), new TreeNode(7))),





                            new TreeNode(3,
                                    null,new TreeNode(8,
                                    new TreeNode(9), null)));
         solution.morris(treeNode);
     }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

  //Definition for a binary tree node.
  public static  class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution {
     List<Integer> ans=new ArrayList<>();
    public List<Integer> preorderTraversal1(TreeNode root) {
        if(root==null) return ans;
        ans.add(root.val);
        if(root.left!=null){
            preorderTraversal1(root.left);
        }
        if(root.right!=null){
            preorderTraversal1(root.right);
        }
        return ans;
    }
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> ans=new ArrayList<>();
        if(root==null) return ans;
        List<TreeNode> stack=new ArrayList<>();
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode node=stack.remove(stack.size()-1);
            ans.add(node.val);
            if(node.right!=null){
                stack.add(node.right);
            }
            if(node.left!=null){
                stack.add(node.left);
            }
        }
        return ans;
    }
    /*Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其前序遍历规则总结如下：
新建临时节点，令该节点为 root；
如果当前节点的左子节点为空，将当前节点加入答案，并遍历当前节点的右子节点；
如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点：
如果前驱节点的右子节点为空，将前驱节点的右子节点设置为当前节点。然后将当前节点加入答案，并将前驱节点的右子节点更新为当前节点。当前节点更新为当前节点的左子节点。
如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空。当前节点更新为当前节点的右子节点。
重复步骤 2 和步骤 3，直到遍历结束。
这样我们利用 Morris 遍历的方法，前序遍历该二叉树，即可实现线性时间与常数空间的遍历。
morris序以例二为例，遍历过程如下：
1 2 4 2 5 6 5 7 1 3 8 9 8
有左孩子的节点会被访问两次，无左孩子的节点只会被访问一次。
则先序遍历是第一次就加入
1 2 4 5 6 7 3 8 9
中序遍历是第二次加入
4 2 6 5 7 1 3 9 8
后续遍历 则需要在第二次访问时 逆序打印他的左树的右边界（包括自己）
最后再逆序打印整棵树的右边界（包括根节点）
依次打印了 2 5 1 8 整棵树 的右边界，4 ，6,7 5 2,9,8 3 1
4 6 7 5 2 9 8 3 1
*/

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        // p1表示当前节点，p2表示前驱节点（最右节点）
        TreeNode p1 = root, p2 = null;

        while (p1 != null) {
            p2 = p1.left;
            //如果有左子树，分两种情况
            if (p2 != null) {
                while (p2.right != null && p2.right != p1) {
                    p2 = p2.right;
                }
                if (p2.right == null) {
                    res.add(p1.val);
                    p2.right = p1;
                    p1 = p1.left;
                    continue;
                } else {
                    p2.right = null;
                }
            } else {
                res.add(p1.val);
            }
            p1 = p1.right;
        }
        return res;
    }

    public List<Integer> morris(TreeNode root) {
        List<Integer> pre = new ArrayList<Integer>();
        List<Integer> post = new ArrayList<Integer>();
        List<Integer> in = new ArrayList<Integer>();
        List<Integer> mo = new ArrayList<Integer>();
        if (root == null) {
            return new ArrayList<>();
        }
        // p1表示当前节点，p2表示前驱节点（最右节点）
        TreeNode cur = root, moiRight = null;
        while (cur != null) {
            mo.add(cur.val);
            moiRight = cur.left;
            //如果有左子树，分两种情况
            if (moiRight != null) {
                //找到左子树的最右节点，且该节点的右子节点不等于当前节点（相当于第一次来）
                while (moiRight.right != null && moiRight.right != cur) {
                    moiRight = moiRight.right;
                }
                // 第一次来，建立连接
                if (moiRight.right == null) {
                    pre.add(cur.val);
                    moiRight.right = cur;
                    cur = cur.left;
                } else {
                    // 第二次来，断开连接
                    in.add(cur.val);
                    moiRight.right = null;
                    addPath(cur.left,post);
                    cur=cur.right;
                }
            } else {
                // 没有左子树，直接访问右子树
                pre.add(cur.val);
                in.add(cur.val);
                cur=cur.right;
            }
        }
        addPath(root,post);
        System.out.println(mo);
        System.out.println(pre);
        System.out.println(in);
        System.out.println(post);
        return new ArrayList<>();
    }
    // 反向收集右边界路径上的节点值
    private void addPath(TreeNode node, List<Integer> res) {
        int count = 0;
        // 步骤1：沿着右指针收集节点，并计数
        while (node != null) {
            ++count;
            res.add(node.val);
            node = node.right;
        }
        // 步骤2：反转刚添加的这部分节点顺序，list可能已经有数字了，每次只把新加的部分反轉，因此确定范围
        int left = res.size() - count, right = res.size() - 1;
        while (left < right) {
            int temp = res.get(left);
            res.set(left, res.get(right));
            res.set(right, temp);
            left++;
            right--;
        }
    }
    // 反轉后收集然後再反轉回去
    private void printEdge(TreeNode node, List<Integer> res) {
        TreeNode tail=reverse(node);
        TreeNode cur=tail;
        while (cur!=null){
            res.add(cur.val);
            cur=cur.right;
        }
        reverse(tail);
    }
}
        // 反轉鏈表
    private TreeNode reverse(TreeNode tail) {
        TreeNode prev=null;
        TreeNode next=null;
        while (tail!=null){
            next=tail.right;
            tail.right=prev;
            prev=tail;
            tail=next;
        }
        return prev;
     }
//leetcode submit region end(Prohibit modification and deletion)

}
